package algorithm.MaxSubarrSum;

/*
给定一个数组arr，返回子数组的最大累加和
 */
public class MaxSubarrSum {
    public static int maxSum(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;

        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            cur += arr[i];
            if (cur < 0)
                cur = 0;
            max = Math.max(max, cur);
        }

        return max;
    }

    public static void main(String[] args) {
        int[] arr = {3, -1, 3, -6, 7, 3, -1, 3, -1};
        int maxSum = maxSum(arr);
        System.out.println(maxSum);
    }
}
